package com.leetcode;

import java.util.Arrays;

public class Leetcode338 {
    /*
    solution 1: Leetcode191 上继续拓展
    public int[] countBits(int n) {
        int[] result = new int[n + 1];
        for (int i = 0; i < n + 1; i++) {
            result[i] = _countBits(i);
        }

        return result;
    }

    private int _countBits(int n) {
        int res = 0;
        while (n != 0) {
            n = n & (n - 1);
            res++;
        }
        return res;
    }
*/
    //solution 2:
    //推理过程：
    // 1） bits(n) 表示 n 二进制位中 1 的个数;
    // 2)  n&(n-1)，表示减去一个1
    // 结论：bits(n) = bits(n&(n-1))+1;
    public int[] countBits(int n) {
        int[] result = new int[n + 1];
        for (int i = 1; i < n + 1; i++) {
            result[i] = result[i & (i - 1)] + 1;
        }

        return result;
    }

    public static void main(String[] args) {
        Leetcode338 leetcode338 = new Leetcode338();
        int[] result = leetcode338.countBits(5);
        System.out.println(Arrays.toString(result));
    }
}
